package org.example.top40;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class main06 {
    //三数之和
    //nums = [-1,0,1,2,-1,-4]
    //[[-1,-1,2],[-1,0,1]]
    //排序  fori循环里有,l，r while sum l，r
    // >0不肯能情况
    //a,b,c判断前一位,是否相同，防止漏掉-1,-1,2
    //wile b,c判断放add后，找到三元组后去重，避免结果重复。判断的是后一位 l+1 r-1
    public static void main(String[] args) {
        int[] nums={-1,0,1,2,-1,-4};
        List<List<Integer>> res=threeSum(nums);
        System.out.println(res);
    }

    private static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                break;
            }
            if(i>0&&nums[i-1]==nums[i]){
                continue;
            }
            int l=i+1;
            int r= nums.length-1;
            while (l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum>0){
                    r--;
                } else if (sum<0) {
                    l++;
                }else {
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    while (l<r&&nums[l]==nums[l+1]){
                        l++;
                    }
                    while (l<r&&nums[r]==nums[r-1]){
                        r--;
                    }
                    l++;
                    r--;
                }
            }
        }
        return res;
    }




    /*public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i>0&&nums[i - 1] == nums[i]) {
                continue;
            }
            int l = i+1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum > 0) {
                    r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    l++;
                    r--;
                }
            }
        }
        System.out.println(res);
    }*/

}
